"""
归并排序(merge sort)
"""

def merge(nums: list[int], left: int, mid: int, right: int) -> None:
    """合并，此时mid两侧的数组已排序。直接修改原数组
    左数组闭区间[left, mid]
    右数组闭区间[mid+1, right]
    [..., 1, 3, 5, 7, 9,   2, 4, 6, 8, ...]
    left=7, mid=11, right=15
    """

    # 切片创建左右数组
    left_list = nums[left: mid + 1]
    right_list = nums[mid + 1: right + 1]

    # 索引
    left_index = 0
    right_index = 0
    sorted_index = left

    # 先排完一个数组
    while left_index < len(left_list) and right_index < len(right_list):
        if left_list[left_index] < right_list[right_index]:
            nums[sorted_index] = left_list[left_index]
            left_index += 1
        else:
            nums[sorted_index] = right_list[right_index]
            right_index += 1
        # 每比较一次，更新一次排好序的索引
        sorted_index += 1

    # 没有排完的元素一定是有序的
    while left_index < len(left_list):
        nums[sorted_index] = left_list[left_index]
        left_index += 1
        sorted_index += 1

    while right_index < len(right_list):
        nums[sorted_index] = right_list[right_index]
        right_index += 1
        sorted_index += 1

def merge_sort(nums: list[int], left, right) -> None:
    """归并排序 划分子问题
    设置这两个参数便于写递归终止条件
    """
    if left >= right:
        return
    # 划分子问题
    mid = (left + right) // 2
    merge_sort(nums, left, mid)
    merge_sort(nums, mid+1, right)
    # 合并
    merge(nums, left, mid, right)


if __name__ == '__main__':
    nums = [7, 9, 8 , 4 , 6 , 3, 4 , 
            1, 3, 5, 7, 9,   # 左数组left=7, mid=11
            2, 4, 6, 8,      # 右数组right=15
            9, 7, 8]
    # merge(nums, left=7, mid=11, right=15)
    # print(nums)
    # print(nums[7:15+1])
    print(nums)
    merge_sort(nums, 0, len(nums) - 1)
    print(nums)
